using System.Text;

namespace DataStructure
{
    public class SortArray1<Key> where Key : IComparable<Key>
    {
        private Key[] keys;
        private int size;
        
        public SortArray1(int capacity)
        {
            keys = new Key[capacity];
        }
        public SortArray1(): this(10){}
        
        public int Count => size;
        public bool IsEmpty => size == 0;
        
        //查找元素所在的索引
        public int Rank(Key key)
		{
    		//在[l~r]范围里寻找key
    		int l = 0;
    		int r = size - 1;

    		while (l <= r)
    		{
        		int mid = l + (r - l) / 2;

        		if (key.CompareTo(keys[mid]) < 0)
            		r = mid - 1;    //mid左侧查找key
        		else if (key.CompareTo(keys[mid]) > 0)
            		l = mid + 1;    //mid右侧查找key
        		else    //key.CompareTo(keys[mid]) == 0
            		return mid;     
    		}

    		return l;//未找到key，返回l
		}
		
		public void Add(Key key)
		{
		    int i = Rank(key);
		    
		    if(size == keys.Length)
		        ResetCapacity(2 * keys.Length);
		        
		    //已经存在于集合中，不操作
		    if(i < size && keys[i].CompareTo(key) == 0)
		        return;
		    
		    for (int j = size-1; j >= i; j--)
		        keys[j+1] = keys[j];
		        
		    keys[i] = key;
		    size++;
		}
		
		public void Remove(Key key)
		{   
		    if(IsEmpty)
		        return;
		    int i = Rank(key);
		    
		    //不在数组||或key不存在
		    if(i == size || keys[i].CompareTo(key) != 0)
		        return;

		    for (int j = i + 1; j <= size - 1; j++)
		        keys[j - 1] = keys[j];

		    size--;
		    keys[size] = default(Key); //防止对象游离
		    
		    if(size == keys.Length / 4)
		        ResetCapacity(keys.Length / 2);
		}
		
		public Key Min()
		{
		    if(IsEmpty)
		        throw new Exception("Array is empty");
		        
		    return keys[0];
		}
		public Key Max()
		{
		    if(IsEmpty)
		        throw new Exception("Array is empty");
		        
		    return keys[size - 1];
		}
		//查询索引位置对应元素
		public Key Select(int k)
		{
		    if (k < 0 || k >= size)
		        throw new Exception("Index is illegal");

		    return keys[k];
		}
		public bool Contains(Key key)
		{
		    int i = Rank(key);

		    if(i < size && keys[i].CompareTo(key) == 0)
		        return true;
		    return false;
		}
		
		 //找出小于或等于key的最大键
		public Key Floor(Key key)
		{
		    int i = Rank(key);
		    
		    if (i < size && keys[i].CompareTo(key) == 0)
		        return keys[i];
		        
		    if (i == 0)
		        throw new ArgumentNullException("没有找到小于或等于" + key + "的最大键元素");
		    else
		        return keys[i - 1];
		}
		//找出大于或等于key的最小键
		public Key Ceiling(Key key)
		{
		    int i = Rank(key);
		    
		    if (i == size)
		        throw new ArgumentNullException("没有找到大于或等于" + key + "的最小键元素");
		    else 
		        return keys[i];
		}
		
		//扩容
		private void ResetCapacity(int newCapacity)
		{
		    Key[] newKeys = new Key[newCapacity];
		    for (int i = 0; i < size; i++)
		        newKeys[i] = keys[i];
		        
		    keys = newKeys;
		}

        public override string ToString()
        {
            StringBuilder res = new StringBuilder();
            res.Append("[");
            for (int i = 0; i < size; i++)
            {
                res.Append(keys[i]);
                if (i != size - 1)
                    res.Append(", ");
            }
            res.Append("]");
            return res.ToString();
        }
    }
}